package com.leetcode.algorithm.y19.m04;

import com.leetcode.algorithm.common.ListNode;

/**
 * leetcode-cn.com
 * 
 * (done)141. 环形链表
 * (done)142. 环形链表 II
 * (done)160. 相交链表
 * (done)19. 删除链表的倒数第N个节点
 * @author: jie.deng
 * @time: 2019年4月16日 上午12:18:44
 */
public class MySolution0416 {
    
    /**
     * 141. 环形链表 
     * 给定一个链表，判断链表中是否有环。
     * 
     * 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。
     * 
     * 示例 1：
     * 输入：head = [3,2,0,-4], pos = 1
     * 输出：true
     * 解释：链表中有一个环，其尾部连接到第二个节点。
     * 
     * 示例 2：
     * 输入：head = [1,2], pos = 0
     * 输出：true
     * 解释：链表中有一个环，其尾部连接到第一个节点。
     * 
     * 示例 3：
     * 输入：head = [1], pos = -1
     * 输出：false
     * 解释：链表中没有环。
     * 
     * 进阶：
     * 
     * 你能用 O(1)（即，常量）内存解决此问题吗？
     * 
     * @param head
     * @return
     */
    public boolean hasCycle(ListNode head) {
        // Initialize slow & fast pointers
        ListNode slow = head;
        ListNode fast = head;
        /**
         * Change this condition to fit specific problem.
         * Attention: remember to avoid null-pointer error
         **/
        while (slow != null && fast != null && fast.next != null) {
            slow = slow.next;           // move slow pointer one step each time
            fast = fast.next.next;      // move fast pointer two steps each time
            if (slow == fast) {         // change this condition to fit specific problem
                return true;
            }
        }
        return false;   // change return value to fit specific problem
    }
    
    /**
     * 142. 环形链表 II
     * 
     * 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
     * 
     * 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。
     * 
     * 说明：不允许修改给定的链表。
     * 
     *  
     * 
     * 示例 1：
     * 
     * 输入：head = [3,2,0,-4], pos = 1
     * 输出：tail connects to node index 1
     * 解释：链表中有一个环，其尾部连接到第二个节点。
     * 
     * 
     * 示例 2：
     * 
     * 输入：head = [1,2], pos = 0
     * 输出：tail connects to node index 0
     * 解释：链表中有一个环，其尾部连接到第一个节点。
     * 
     * 
     * 示例 3：
     * 
     * 输入：head = [1], pos = -1
     * 输出：no cycle
     * 解释：链表中没有环。
     * 
     * 
     *  
     * 
     * 进阶：
     * 你是否可以不用额外空间解决此题？
     * @param head
     * @return
     */
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        // 找出环的长度i
        int i = 0;
        while (slow != null && fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            i++;
            if (slow == fast) {
                break;
            }
        }
        if (fast==null || fast.next == null || slow != fast) {
            // 无环
            return null;
        }
        slow = head;
        fast = head;
        // fast先走i步
        while (i > 0) {
            fast = fast.next;
            i--;
        }
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }
    
    /**
     * 160. 相交链表
     * 编写一个程序，找到两个单链表相交的起始节点。
     * 
     *  例如，下面的两个链表：
     *  A:          a1 → a2
     *                      ↘
     *                       c1 → c2 → c3
     *                      ↗            
     *  B:     b1 → b2 → b3
     *  在节点 c1 开始相交。
     *
     *  注意：
     *  如果两个链表没有交点，返回 null.
     *  在返回结果后，两个链表仍须保持原有的结构。
     *  可假定整个链表结构中没有循环。
     *  程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。
     * @param headA
     * @param headB
     * @return
     */
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        // 计算链表的长度
        int lenA = 0;
        int lenB = 0;
        ListNode curA = headA;
        while (curA != null) {
            lenA++;
            curA = curA.next;
        }
        ListNode curB = headB;
        while (curB != null) {
            lenB++;
            curB = curB.next;
        }
        // 链表长度较长者，先走N步，使剩余链表长度相等
        curA = headA;
        curB = headB;
        if (lenA > lenB) {
            int i = lenA - lenB;
            while (i > 0) {
                curA = curA.next;
                i--;
            }
        } else if (lenB > lenA) {
            int i = lenB - lenA;
            while (i > 0) {
                curB = curB.next;
                i--;
            }
        }
        // 从剩余链表中找相交的起始节点
        int i = Math.min(lenA, lenB);
        while (i > 0) {
            if (curA == curB) {
                return curA;
            }
            curA = curA.next;
            curB = curB.next;
            i--;
        }
        return null;
    }
    
    /**
     * 19. 删除链表的倒数第N个节点
     * 
     * 给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
     * 
     * 示例：
     * 
     * 给定一个链表: 1->2->3->4->5, 和 n = 2.
     * 
     * 当删除了倒数第二个节点后，链表变为 1->2->3->5.
     * 说明：
     * 
     * 给定的 n 保证是有效的。
     * 
     * 进阶：
     * 
     * 你能尝试使用一趟扫描实现吗？
     * @param head
     * @param n
     * @return
     */
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode n0 = null; // 待删除结点的父节点
        ListNode n2 = head; // 与待删除结点的父结点相隔n个结点
        while (n > 1) {
            n2 = n2.next;
            n--;
        }
        // 找到最后一个结点n2 和 倒数第 n个节点的父节点n0
        while (n2.next != null) {
            if (n0 == null) {
                n0 = head;
            } else {
                n0 = n0.next;
            }
            n2 = n2.next;
        }
        // 删除倒数第 n个节点
        if (n0 == null) {
            return head.next;
        }
        n0.next = n0.next.next;
        return head;
    }
}
